package com.zbxx.leetcode.tree;


import com.zbxx.leetcode.struct.TreeNode;

import java.util.Deque;
import java.util.LinkedList;

/**
 * 623 在二叉树增加一行
 *
 * @author wanrj
 * @date 2023/6/7
 */
public class addOneRow {


    public TreeNode addOneRow(TreeNode root, int val, int depth) {
        if (depth == 1) {
            TreeNode r = new TreeNode(val);
            r.left = root;
            return r;
        }
        Deque<TreeNode> preDepth = new LinkedList<>();
        Deque<TreeNode> deque = new LinkedList<>();
        deque.add(root);
        deque.add(null);
        int d = 1;
        while (!deque.isEmpty()) {
            TreeNode n = deque.poll();
            if (n == null) {
                d++;
                if (!deque.isEmpty()) {
                    deque.offer(null);
                }
                if (d == depth) {
                    while (!preDepth.isEmpty()) {
                        TreeNode pre = preDepth.poll();
                        TreeNode l = pre.left;
                        TreeNode r = pre.right;
                        TreeNode nl = new TreeNode(val);
                        TreeNode nr = new TreeNode(val);
                        pre.left = nl;
                        nl.left = l;
                        pre.right = nr;
                        nr.right = r;
                    }
                }
                preDepth.clear();
                continue;
            }
            preDepth.offer(n);
            if (n.left != null) {
                deque.offer(n.left);
            }
            if (n.right != null) {
                deque.offer(n.right);
            }
        }
        return root;
    }

    public static void main(String[] args) {
        TreeNode t = new TreeNode(4);
        t.left = new TreeNode(2);
        t.right = new TreeNode(6);
        t.right.left = new TreeNode(5);
        t.left.left = new TreeNode(3);
        t.left.right = new TreeNode(1);
        System.out.println(new addOneRow().addOneRow(t, 1, 3));
    }

}
